POJ_3320

题意

给一个数字串，求最短连续串包括含了所有元素，求长度

思路

双指针法其实就是尺取法的思想演变而来的

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
using namespace std;
#define NV 100005
#define ll long long
ll s,a[1000050];
int n,t,tmp;
set <int >st;
//尺取法，复杂度 O(n*logn)
//突然发现双指针法用的也是尺取法的思想啊
int solve_1(){
    int cnt = st.size(),i=1,j=1,num=0,ret=1e8;
    map <int ,int >mp;
    while(1){
        while(j <= n && num < cnt)
            if(mp[a[j++]]++==0)num++;
        if(num < cnt)break;
        while(--mp[a[i++]]!=0);
        num--;
        ret = min(ret , j-i+1);
    }
    return ret;
}
int main(){ 
    cin>>n;
    for(int i=1 ; i<=n ;i++){
        scanf("%d",&tmp);
        st.insert(tmp);
        a[i]=tmp;
    }
    printf("%d\n",solve_1());
    return 0;
}